1. Field of the Invention
The present invention relates generally to caching objects and in particular to caching objects that are related to a common host computer system.
2. Background of the Invention
The Internet is a world-wide collection of interconnected networks that is widely used to access information. A web server is an Internet-connected computer system that can provide information to Internet-connected client computers. Client computers use a computer program called a web browser to connect to and access information on web servers. Using a web browser, a user of an Internet-connected computer can access a huge number of different web servers. The vast collection of web servers available on the Internet is frequently referred to as the World Wide Web.
A web browser displays information received from a web server in units that have the appearance of pages, and because of their appearance, the pages downloaded from web servers and displayed by web browsers are frequently referred to as web pages. Web pages may contain references to elements including formatted text, images, and program code. The web pages and the referenced elements, such as image files and HTML documents, are sometimes called web objects. For example, when a web page contains a reference to a graphical image that should be displayed with the web page, the web page contains a reference to a graphic file. The graphic file and the file containing the information about the web page are called web objects. A general term for an information entity is xe2x80x9cobject.xe2x80x9d
As Internet access becomes more popular, less expensive and faster, and as the number of web clients increases, so does the number of connections made to particular origin servers. This increased number of connections can increase both network load and server load, sometimes causing parts of the Internet and particular origin servers to become so overloaded that they become inaccessible. Caching can be used to improve this situation.
A caching server may be used as an intermediary between a client and an origin server. Instead of a service request message being sent to an origin server, the message is routed to a proxy server. The proxy server handles the request by forwarding it to the origin server, receiving the requested information from the origin server, and transmitting the requested information to the client.
To expedite retrieval of requested information, a conventional proxy server often stores retrieved information in a local cache in the proxy server. When the proxy server receives a service request message from a client, it first determines whether the information requested by the service request message is already stored locally in the proxy server cache. If the requested information is stored in the proxy server cache, it is retrieved from the cache and returned to the client. If the information is not stored in the proxy server cache, the proxy server requests the information from the origin server. When the proxy server receives the requested information from the origin server, it sends the information to the client and also caches the information in the local proxy server cache. Caching can alternatively or additionally be done at other locations in a network. For example, a web browser can cache information locally at the client.
Various mechanisms for caching data are used in computer systems to reduce system loads by storing copies of frequently accessed information in places closer to where the information is likely to be needed. In response to a request from an information requester, a cache system determines whether the information is cached. If not, it is called a cache miss, and the cache system requests the information from the appropriate information provider, also saving a copy of the information in its local cache. If the information is already in the cache, it is called a cache hit. In either case, the information is then forwarded to the requester. By thus reducing loads and locating data closer to where it is needed, caching systems make data access more efficient.
Cache systems can improve the speed of information transfer between an information requester and an information provider. Cache systems generally include a high speed memory, such as, for example RAM, that stores information that was most recently requested from an information provider. A cache is often used in networks to expedite transferring information between a client and an origin server.
A protocol defines how the client and origin server communicate. The Internet, for example, uses protocols such as the Hypertext Transfer Protocol (xe2x80x9cHTTPxe2x80x9d) to transfer web objects. In HTTP, a client sends a service request message to an origin server. For example, a service request message may include a request method to be performed on an object in the origin server. The object may be identified in the service request message by a name or an identifier of the object. In one embodiment, an object is represented as a web page and the identifier is a uniform resource locator (xe2x80x9cURLxe2x80x9d), which is a path to the object. The origin server responds to the service request message by performing the method in the request method. The request method may be a retrieve operation, which causes the origin server to retrieve the object identified by the URL, and transmit it to the requesting client.
Since the number of available documents in the web is huge, it is advantageous for a web caching system to use a large cache to increase the likelihood of a web hit. However, filling up a large cache with web objects may take a long time, potentially longer than acceptable, and it is therefore important to preserve the contents of a large cache during and after a system shutdown. Therefore, most web caching systems store cached web objects in a large but slow persistent storage, such as disk drives. Unfortunately, reading data from or writing data to a disk is slow, much slower than access to fast main memory. To reduce the delays associated with requests for web objects cached on disk drives, known caching systems use a fast-main-memory cache that is generally smaller than the persistent cache to store copies of web objects that are deemed most likely to be requested in the immediate future.
Typically, a web client accesses many pages from an origin server, one page at a time. Each page may refer to many other web objects including images and text. Typical web objects may be as small as 10 K bytes, or even smaller. To access a complete page that has not been previously cached by a web caching system, i.e. a cache miss, many separate requests must be made by a web browser. In the HTTP protocol, for example, this results in a separate request for each web object that is associated with a web page. Thus a cache miss for a web page usually results in one or more writes to disk for storing the retrieved objects referenced in the page. Similarly a cache hit for a page that is not in the fast main memory cache may result in one or more reads to the disk to retrieve each web object referenced in the page. Thus, requesting a web object that is not in the fast main memory cache always results in at least one disk input or output (xe2x80x9cI/Oxe2x80x9d) operation, a minimum of one disk write for a cache miss and a minimum of one disk read for a cache hit. Since there are typically multiple web objects associated with a particular web page, this means that there will typically be multiple disk I/O operations associated with the caching or serving of a web page.
Disk access is significantly slower than fast main memory access. Typically, a disk can handle a small number of I/O operations per second. Since a cache hit or a cache miss for a web object usually results in at least one disk I/O, the cache throughput (number of web client requests that can be handled per second) of a web caching system is limited by the total number of I/O operations that can be supported by the disks used in the caching system. Thus, in some caching systems, disk access is the biggest bottleneck in maximizing cache throughput.
Strategically adding hardware to a caching system can increase the cache throughput. For example, if a larger fast-main-memory cache is used, more web objects may be stored in fast main memory, thereby reducing a probability of having to access a disk to retrieve a stored web object. Similarly, web objects may be distributed over multiple disks, thereby allowing multiple concurrent disk accesses and increasing the number of client requests that can be processed per second. While persistent storage devices are each relatively slow, they can operate in parallel, thereby increasing the total number of I/O operations per second.
Unfortunately, adding hardware to a caching system also increases the cost of the system. It is therefore advantageous to employ a design that improves caching throughput without depending on additional hardware. It is also desirable for such a design to scale-up in caching throughput with the use of additional hardware.
Consistent with the present invention, systems, methods, and computer-readable media are involved in caching of related objects. A plurality of objects is received from at least one origin server. A hash value is computed corresponding to source identifying information for at least one object in the plurality of objects. In at least one data structure of a plurality of data structures, the object is stored based on the computed hash value, the object being stored with related objects having related hash values.
Additional benefits of the invention will be set forth in part in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The benefits of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the appended claims.
It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention, as claimed.